package 图.树;

import org.junit.Test;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/16 21:27
 */
public class 数组模拟二叉树 {
    /*
     对比 算法岗, 来说
     研发岗 的题,反而 更加的 难些
     https://leetcode.cn/circle/discuss/BbSSH1/
     上面有大佬, 写的差不多了,
     把前两题给整明白!

     牛客链接:
     https://www.nowcoder.com/discuss/465908950907506688?sourceSSR=search
     */



    /*
     判断 一个 二叉树 是不是 满二叉树, 下面这种好像 更简单一些, 当前节点是满二叉树, 需要: 左子树 满二叉树, 右子树满二叉树, 左子树的height = 右子树的 height (这样的话 树形dp 的方式会更加简单一些)
     // dfs，遍历编号为u的节点
        // 如果是满二叉树，返回其对应的深度，否则返回0
        int dfs(int u) {
            // 当前u节点是一个叶子结点，一定满足满二叉树
            if(d[u][0] == -1 && d[u][1] == -1) {
                res.push_back(u);
                return 1;
            }
            // 只存在一个孩子节点为空，则不是满二叉树
            if(d[u][0] == -1 || d[u][1] == -1) return 0;
            // 左右孩子一定不为空，递归判断
            int left = dfs(d[u][0]), right = dfs(d[u][1]);
            // 左右孩子都是满二叉树，而且深度相等，当前节点才是满二叉树
            if(left && right && left == right) {
                res.push_back(u);
                return left + 1;
            }
            return 0;
        }

     */




    /*
     用两种方式来写一下,
     1. 用数组, 来模拟这个二叉树
     那对于 一个 图, 来说好像使用 数组表示 ,这种方式,有那么一点点的熟悉了!
     int[][] binaryTree = new int [n][2];
     int [][] map = new int [n][]; // 直接不指定 第二个维度的长度, 因为图的 后继节点, 不能像二叉树那样直接 就确定为 2


     2. 直接用构建出这颗二叉树
     */

    public int solution() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int inDgree[] = new int[n + 1];
        int[][] tree = new int[n + 1][2]; // tree[i][0] 表示左节点, tree[i][1] 表示右节点
        for (int i = 1; i <= n; i++) {
            tree[i][0] = sc.nextInt();
            tree[i][1] = sc.nextInt();
            if(tree[i][0] != -1){
                inDgree[tree[i][0]]++;
            }
            if(tree[i][1] != -1){
                inDgree[tree[i][1]]++;
            }
        }

        /*
         该题 并未说明 1 号 节点 是 根节点,
         所有还需要进行二叉树根节点的判断
         判断的根据, 就是 只有根节点的  入度 为 0, 先计算所有几点的一个 入度,
         然后 找出 入度为0
         将 这个数组的 初始化,直接放在 sc.nextInt() 中
         */
//        for(int i = 1;i <= n;i++){
//            inDgree[tree[i][0]]++;
//            inDgree[tree[i][1]]++;
//        }
        int root;
        for(int i = 1;i <= n;i++){
            if(inDgree[i] == 0){
                root = i;
                break;
            }
        }
        return recursion(tree,1)[0];
    }

    public int[] recursion(int tree[][], int root) {
        if (root == -1) {
            return new int[]{0, 0, 0}; // 下标0 : 完全二叉树的个数, 下标1 : 表示的是 树的高度 ,下标2 : 表示的 节点数
        }
        int leftData[] = recursion(tree,tree[root][0]);
        int rightData[] = recursion(tree,tree[root][1]);
        // 封装当前层的 信息, 返回给上层
        int count = leftData[0] + rightData[0];
        int height = Math.max(leftData[1],rightData[1]) + 1;
        int nodes = leftData[2] + rightData[2] + 1;
        // 判断 以当前 节点,为root,是不是完全二叉树, 如果是 count + 1,不是 count 不变
        count += nodes == (1 << height) - 1 ? 1 : 0;
        return new int[]{count,height,nodes};
    }

    public static void main(String[] args) {
        int solution = new 数组模拟二叉树().solution();
        System.out.println(solution);
    }

    public void function(int tree[][],int root){
        if(root == -1){
            return ;
        }
        System.out.println(root);
        function(tree,tree[root][0]);
        function(tree,tree[root][1]);
    }


    /*
     上面的 方式是完全, 不用构建一棵二叉树
     下面是构建一棵 二叉树, 思路是完全一样的, 只不过
     主要是熟练这个 构建二叉树的过程 (不得不说上面这种 , 用数组表示二叉树的 方式 真的 方便)
     明白怎么构建
     */



    @Test
    public void test(){
        int map[][] = new int[3][];
        // 需要 提前 为 数组的 二维开辟 空间, 否则 不能使用!
        /*
         假如 使用这种方式, 来建图的话, 需要注意这一点!
         */
        map[0] = new int[]{1,2,3};
//        map[1][0] = 1;
//        map[1][1] = 2;
//        map[1][3] = 3;

        map[2] = new int[2];

        for(int num[] : map){
            System.out.println(Arrays.toString(num));
        }
    }

}